package argo.hot100.linklist;

import java.util.HashMap;
import java.util.Map;

public class LRUCache {

    class DLinkListNode {
        DLinkListNode pre;
        DLinkListNode next;
        Integer key;
        Integer val;

        DLinkListNode() {
        }

        DLinkListNode(Integer k, Integer v) {
            this.key = k;
            this.val = v;
        }
    }

    Map<Integer, DLinkListNode> map = new HashMap<>();

    DLinkListNode dLinkHead = new DLinkListNode();
    DLinkListNode dLinkTail = new DLinkListNode();

    Integer size = 0;

    public LRUCache(int capacity) {
        size = capacity;
        dLinkHead.next = dLinkTail;
        dLinkHead.pre = null;
        dLinkTail.pre = dLinkHead;
        dLinkTail.next = null;
    }

    public int get(int key) {

        if (map.get(key) != null) {
            DLinkListNode node = map.get(key);
            removeElement(node);
            addElementToHead(node);
            return node.val;
        } else {
            return -1;
        }

    }

    public void put(int k, int v) {


        if (map.containsKey(k)) {
            DLinkListNode node = map.get(k);
            node.val = v;
            map.put(k, node);
            removeElement(node);
            addElementToHead(node);

        } else {
            DLinkListNode newNode = new DLinkListNode(k, v);
            if (map.size() < size) {
                map.put(k, newNode);
                addElementToHead(newNode);
            } else {

                DLinkListNode delNode = removeElementFromLast();
                map.remove(delNode.key);
                addElementToHead(newNode);
                map.put(k, newNode);
            }
        }

    }

    void addElementToHead(DLinkListNode newNode) {

        newNode.next = dLinkHead.next;
        dLinkHead.next.pre = newNode;
        dLinkHead.next = newNode;
        newNode.pre = dLinkHead;

    }

    DLinkListNode removeElementFromLast() {
        DLinkListNode node = dLinkTail.pre;
        dLinkTail = dLinkTail.pre;
        dLinkTail.next = null;
        return node;
    }

    void removeElement(DLinkListNode node) {
        node.next.pre = node.pre;
        node.pre.next = node.next;
    }
}
